The present invention relates generally to image processing, and more particularly to optimizing computation of morphology operations in both binary and grayscale applications.
Mathematical morphology is used in a variety of digital image processing applications, such as computer vision and medical imaging applications (e.g., for segmentation and skeletonization tasks). For example, medical personnel may perform a Computed Tomography (CT) scan on a patient. A CT scan uses x-ray equipment to obtain image data from different angles around the human body and then processes the data to show a cross-section of the body tissues and organs. The image can then be analyzed by methods using morphological operators to highlight specific areas so that radiologists (or other medical personnel) can more easily diagnose problems associated with the patient such as cancers, cardiovascular disease, infectious disease, trauma and musculoskeletal disorders.
This type of image analysis occurs by applying morphological operators (also referred to as structuring elements (SE)) to the image. SEs of different scales can be used as during a step in performing airway or vessel segmentation. Skeletonization methods depend on repeated applications of morphological operators to compute the medial axis of given objects.
To apply a structuring element to an input image, the structuring element is traversed along the input image and an operation is performed. The fundamental morphology operations are dilation and erosion. Binary dilation is performed by computing the logical OR of the neighborhood defined by the structuring element (also referred to as a filter kernel) with respect to each pixel/voxel of the input image and assigning that value to the center of the operator. Binary erosion is performed by computing the logical AND operation of the neighborhood defined by the structuring element with respect to each pixel/voxel of the input image. In the case of gray level images, the logical OR/AND is replaced by the MAX/MIN operator to produce gray level dilation/erosion. The logical AND/OR operators along with the MAX/MIN operators are collectively referred to as comparison operators.
FIG. 1 shows an example of a 3×3 square structuring element 100 being applied to an input image 104. The operation being performed is a binary dilation, which is performed by computing the logical OR of the neighborhood defined by the structuring element 100 with respect to each pixel of the input image 104. To perform the dilation, the center pixel 108 of the SE 100 is positioned at each pixel of the input image 104 and the SE 100 takes the place of the input image pixel when the OR operator is non-zero. To put it differently, the structuring element 100 specifies which pixels of the input image 104 to OR together. Thus, the dilation operator results in an output image 112 that contains more non-zero pixels than the input image 104. The shaded pixels 116 represent the pixels that have been added as a result of the operation while the white pixels 118 are from the original input image 104. The image 112 is surrounded by pixels 120 that are “off”—that have a zero binary value and are not part of the image (i.e., pixels that are “on”).
FIG. 1 also shows an example of the same square SE 100 being applied to the same input image 104 under binary erosion. As described, binary erosion uses a logical AND operation between the structuring element 100 and the input image 104. The output image 120 contains less “on” pixels relative to the input image 104. In this example, all that is left is a single pixel since there is only one location within the input image where the operator is encompassed by the image, leading to a true value for the AND operation. The image 120 is surrounded by pixels 124 that are off (i.e., have a zero binary value).
The direct application of these morphology operations is computationally intensive. In particular, the computation time needed by a computer is directly proportional to the number and type of computational operations performed, which in turn is proportional to the product of SE and image sizes. In order to have results in a timely fashion, an efficient algorithm is necessary. Otherwise, one is limited in the size of the SE or input image.
There are several algorithms that may be used to perform a morphological operation. The simplest approach is the brute force algorithm. The brute force algorithm examines all pixels/voxels within the SE per pixel computed. The results are stored onto a different image. The computation time of the brute force algorithm depends on the “digital mass” of the structuring element. The digital mass refers to the number of pixels within specified confines in the context of a two-dimensional (i.e., 2-D) geometry (i.e., its discrete area) or the number of voxels within a specified three-dimensional (i.e., 3-D) geometry (i.e., its discrete volume). Thus, in the brute force algorithm, each output pixel requires a number of operations that is equal to the digital mass of the structuring element minus one (the center pixel). Specifically, as the square structuring element 100 has a length and width of three pixels, the number of operations (also referred to below as ops) needed to obtain each pixel of the output image 112, 120 using this structuring element 100 is the area of the square structuring element 100 minus one (i.e., 8 ops). Moreover, if larger and larger structuring elements are used to obtain different output images, the amount of computational time increases exponentially. For example, as the diameter (side length) of a square structuring element increases linearly, the computation time increases proportional to the square of its diameter. For a cube, the computation time increases by the cube of its side as the side-length of the cube increases linearly.
Another technique to perform morphological operations is the factorization algorithm (e.g., homotopic decomposition). The factorization algorithm uses “fundamental” structuring elements. These fundamental structuring elements are used to “break down” larger structuring elements. Hence, instead of applying one large SE to an image, a series of fundamental SEs are used instead. The final outcome is the same, but the computational is reduced since the number of operations necessary for smaller SEs is less than that for one single large SE. For example, suppose a structuring element is a radius 2 cube. Under the brute force algorithm, 53−1=124 ops are needed per output image voxel. Using the factorization algorithm, however, (33−1)*2=52 ops per output image voxel are needed. With factorization, the computational expense is proportional to the discrete diameter of the cube that bounds the considered structuring element rather than its digital mass. Thus, the factorization algorithm provides significant computational savings with respect to the brute force technique.
The factorization algorithm also, however, has a major pitfall—the shape of larger structuring elements that the algorithm can be used on without approximation is severely limited and bounded by the fundamental structuring elements used. For example, a two dimensional digitized circle structuring element or a three dimensional sphere structuring element are the shapes often used to perform medical image processing due to the structure of the human body (e.g., the airway). The factorization algorithm, however, typically cannot be used on a circular or spherical structuring element without excessive complexity because of the shape of the possible fundamental structuring elements relative to the shape of a digitized circle or sphere. Hence, for practical purposes, the best possible outcome is an approximation of a circle or sphere.
As a result, there remains a need to reduce computational time, especially for circles and spheres, when performing morphological operators without constraining the shape of a structuring element.